package leetcode.biweekly.week101;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//Solution4Test
public class Solution4 {
	public int findShortestCycle(int n, int[][] edges) {
		List<List<Integer>> nexts = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			nexts.add(new ArrayList<>());
		}
		for (int[] e : edges) {
			int a = e[0], b = e[1];
			nexts.get(a).add(b);
			nexts.get(b).add(a);
		}
		int ans = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			int cur = bfs(i, nexts, n);
			ans = Math.min(ans, cur);
		}
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}

	private int bfs(int i, List<List<Integer>> nexts, int n) {
		Integer been[] = new Integer[n];
		Queue<Integer> queue = new LinkedList<>();
		queue.add(i);
		been[i] = 0;
		int cnt = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			cnt += 1;
			while (size > 0) {
				int cur = queue.poll();
				for (int next : nexts.get(cur)) {
					if (been[next] == null) {
						queue.add(next);
						been[next] = cnt;
					} else if (been[next] >= cnt - 1) {
						if (been[next] == cnt) {
							return cnt << 1;
						} else {
							return (cnt - 1) * 2 + 1;
						}
					}
				}
				size--;
			}
		}
		return Integer.MAX_VALUE;
	}

}
